/*!
 * Copyright (c) Microsoft Corporation and contributors. All rights reserved.
 * Licensed under the MIT License.
 */

import { strict as assert } from 'assert';

import { take } from '@fluid-private/stochastic-test-utils';
import { MockLogger } from '@fluidframework/telemetry-utils/internal';
import { validateAssertionError } from '@fluidframework/test-runtime-utils/internal';
import { expect } from 'chai';
import { v4, v5 } from 'uuid';

import { assertNotUndefined, fail } from '../Common.js';
import {
	FinalCompressedId,
	LocalCompressedId,
	OpSpaceCompressedId,
	SessionId,
	SessionSpaceCompressedId,
	StableId,
} from '../Identifiers.js';
import { assertIsStableId, generateStableId, isStableId } from '../UuidUtilities.js';
import {
	IdCompressor,
	hasOngoingSession,
	isFinalId,
	isLocalId,
	legacySharedTreeInitialTreeId,
} from '../id-compressor/IdCompressor.js';
import { getIds } from '../id-compressor/IdRange.js';
import {
	createSessionId,
	incrementUuid,
	numericUuidFromStableId,
	stableIdFromNumericUuid,
} from '../id-compressor/NumericUuid.js';
import type { IdCreationRange, UnackedLocalId } from '../id-compressor/index.js';

import {
	Client,
	DestinationClient,
	IdCompressorTestNetwork,
	MetaClient,
	attributionIds,
	createCompressor,
	expectSerializes,
	generateCompressedIds,
	makeOpGenerator,
	performFuzzActions,
	roundtrip,
	sessionIds,
	sessionNumericUuids,
} from './utilities/IdCompressorTestUtilities.js';
import { expectAssert, expectDefined } from './utilities/TestCommon.js';

describe('IdCompressor', () => {
	it('detects invalid cluster sizes', () => {
		const compressor = createCompressor(Client.Client1, 1);
		assert.throws(
			() => (compressor.clusterCapacity = -1),
			validateAssertionError('Clusters must have a positive capacity')
		);
		assert.throws(
			() => (compressor.clusterCapacity = 0),
			validateAssertionError('Clusters must have a positive capacity')
		);
		assert.throws(
			() => (compressor.clusterCapacity = IdCompressor.maxClusterSize + 1),
			validateAssertionError('Clusters must not exceed max cluster size')
		);
	});

	it('reports the proper session ID', () => {
		const sessionId = createSessionId();
		const compressor = new IdCompressor(sessionId, 0);
		expect(compressor.localSessionId).to.equal(sessionId);
	});

	it('accepts different numbers of reserved IDs', () => {
		for (const reservedIdCount of [0, 1, 5]) {
			const compressor = new IdCompressor(createSessionId(), reservedIdCount);
			if (reservedIdCount > 0) {
				expect(compressor.decompress(compressor.getReservedId(0))).to.equal(legacySharedTreeInitialTreeId);
			}
		}
	});

	describe('ID Generation', () => {
		it('can create a compressed ID with an override', () => {
			const compressor = createCompressor(Client.Client1);
			const override = 'override';
			const id = compressor.generateCompressedId(override);
			expect(compressor.decompress(id)).to.equal(override);
		});

		it('can create compressed IDs with v5 overrides', () => {
			const compressor = createCompressor(Client.Client1);
			const uuidA = v5('foo', '7834b437-6e8c-4936-a1a3-0130b1178f17');
			const uuidB = uuidA.slice(0, uuidA.length - 1) + (uuidA.endsWith('a') ? 'b' : 'a');
			const idA = compressor.generateCompressedId(uuidA);
			const idB = compressor.generateCompressedId(uuidB);
			expect(compressor.decompress(idA)).to.equal(uuidA);
			expect(compressor.decompress(idB)).to.equal(uuidB);
		});

		it('can manually create a compressed ID', () => {
			const compressor = createCompressor(Client.Client1);
			const id = compressor.generateCompressedId();
			const uuid = compressor.decompress(id);
			expect(id).to.equal(compressor.recompress(uuid));
		});

		it('will not decompress IDs it did not compress', () => {
			const errorMessage = 'Compressed ID was not generated by this compressor';
			const compressor = createCompressor(Client.Client1);
			assert.throws(() => compressor.decompress(-1 as LocalCompressedId), validateAssertionError(errorMessage));
			assert.throws(
				() => compressor.decompress(compressor.reservedIdCount as FinalCompressedId),
				validateAssertionError(errorMessage)
			);
		});

		it('will not re-compress uuids it did not originally compress', () => {
			const compressor = createCompressor(Client.Client1);
			expect(compressor.tryRecompress('5fff846a-efd4-42fb-8b78-b32ce2672f99')).to.be.undefined;
		});

		it('unifies duplicate overrides originating from the same compressor', () => {
			const override = 'override';
			const compressor = createCompressor(Client.Client1, 3);

			// Client1 compresses a uuid
			const localId1 = compressor.generateCompressedId(override);
			const localId2 = compressor.generateCompressedId(override);
			expect(localId1).to.equal(localId2, 'only one local ID should be allocated for the same override');
			expect(compressor.decompress(localId1)).to.equal(override, 'override incorrectly associated with local ID');
		});

		it('unifies overrides with sequential local IDs', () => {
			const compressor = createCompressor(Client.Client1, 3);

			// Client1 compresses a uuid
			compressor.generateCompressedId();
			const localId2 = compressor.generateCompressedId();
			const stableId2 = assertIsStableId(compressor.decompress(localId2));
			const localId3 = compressor.generateCompressedId(stableId2);
			expect(localId3).to.equal(localId2, 'only one local ID should be allocated for the same sequential uuid');
		});

		it('unifies overrides with sequential local IDs that sort before the reserved session UUID', () => {
			// This is a regression test for an issue where passing a sequential UUID that sorted before the reserved UUID
			// as an override created duplicate overrides in the compressor.
			const newSession = `0${legacySharedTreeInitialTreeId.slice(1)}` as SessionId;
			const compressor = new IdCompressor(newSession, 1 /* just needs to be > 0 */);

			// Client1 compresses a uuid
			compressor.generateCompressedId();
			const localId2 = compressor.generateCompressedId();
			const stableId2 = assertIsStableId(compressor.decompress(localId2));
			const localId3 = compressor.generateCompressedId(stableId2);
			expect(localId3).to.equal(localId2, 'only one local ID should be allocated for the same sequential uuid');
		});

		it('unifies overrides with sequential local IDs that sort after an existing override', () => {
			// This is a regression test for an issue where passing a sequential UUID that sorted after an existing override
			// as an override created duplicate overrides in the compressor.
			const newSession = `b${v4().slice(1)}` as SessionId;
			const compressor = new IdCompressor(newSession, 0);

			// Client1 compresses a uuid with some override that will sort before the session uuid
			compressor.generateCompressedId(`a${v4().slice(1)}`);
			const localId2 = compressor.generateCompressedId();
			const stableId2 = assertIsStableId(compressor.decompress(localId2));
			const localId3 = compressor.generateCompressedId(stableId2);
			expect(localId3).to.equal(localId2, 'only one local ID should be allocated for the same sequential uuid');
		});

		it('unifies overrides with sequential local IDs that sort after an existing cluster', () => {
			// This is a regression test for an issue where passing a sequential UUID that sorted after an existing cluster
			// as an override created duplicate overrides in the compressor.
			const newSession1 = `c${v4().slice(1)}` as SessionId;
			const newSession2 = `b${v4().slice(1)}` as SessionId;
			const compressor1 = new IdCompressor(newSession1, 0);
			const compressor2 = new IdCompressor(newSession2, 0);
			compressor1.clusterCapacity = 5;
			compressor2.clusterCapacity = 5;

			compressor2.generateCompressedId(); // one ID, enough to make a cluster
			compressor1.finalizeCreationRange(compressor2.takeNextCreationRange());

			const localId = compressor1.generateCompressedId();
			const stableId2 = assertIsStableId(compressor1.decompress(localId));
			const localId3 = compressor1.generateCompressedId(stableId2);
			expect(localId3).to.equal(localId, 'only one local ID should be allocated for the same sequential uuid');
		});

		it('unifies unfinalized local overrides with final IDs from a remote session', () => {
			const compressor1 = createCompressor(Client.Client1, 3);
			const compressor2 = createCompressor(Client.Client2, 3);

			const override = 'override';
			const local1 = compressor1.generateCompressedId(override);
			const local2 = compressor2.generateCompressedId(override);
			const creationRange = compressor2.takeNextCreationRange();
			compressor1.finalizeCreationRange(creationRange);
			compressor2.finalizeCreationRange(creationRange);

			expect(compressor1.decompress(local1)).to.equal(override);
			const final1 = compressor1.normalizeToOpSpace(local1);
			const final2 = compressor2.normalizeToOpSpace(local2);
			expect(isFinalId(final1)).to.be.true;
			expect(final1).to.equal(final2);
		});

		it('unifies overrides with sequential local IDs that have been finalized', () => {
			const compressor = createCompressor(Client.Client1);
			const id = compressor.generateCompressedId();
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			const stableId = assertIsStableId(compressor.decompress(id));
			const localId2 = compressor.generateCompressedId(stableId);
			expect(localId2).to.equal(id, 'only one local ID should be allocated for the same sequential uuid');
		});
	});

	describe('can enumerate all locally created IDs', () => {
		const idCount = 10;
		it('created without finalization', () => {
			const compressor = createCompressor(Client.Client1, idCount);
			const ids: SessionSpaceCompressedId[] = [];
			for (let i = 0; i < idCount; i++) {
				ids.push(compressor.generateCompressedId());
			}
			const returnedIds = [...compressor.getAllIdsFromLocalSession()];
			expect(returnedIds).to.deep.equal(ids);
		});

		it('created with finalization', () => {
			const compressor = createCompressor(Client.Client1, idCount);
			const ids: SessionSpaceCompressedId[] = [];
			for (let i = 0; i < idCount; i++) {
				if (i === Math.floor(idCount / 2)) {
					compressor.finalizeCreationRange(compressor.takeNextCreationRange());
				}
				ids.push(compressor.generateCompressedId());
			}
			const returnedIds = [...compressor.getAllIdsFromLocalSession()];
			expect(returnedIds).to.deep.equal(ids);
		});

		it('created with expanded finalization', () => {
			const compressor = createCompressor(Client.Client1, idCount);
			const ids: SessionSpaceCompressedId[] = [];
			for (let i = 0; i < idCount * 4; i++) {
				if (i !== 0 && i % Math.floor(idCount / 3) === 0) {
					compressor.finalizeCreationRange(compressor.takeNextCreationRange());
				}
				ids.push(compressor.generateCompressedId());
			}
			const returnedIds = [...compressor.getAllIdsFromLocalSession()];
			expect(returnedIds).to.deep.equal(ids);
		});

		it('created with overrides', () => {
			const capacity = 100;
			const compressor = createCompressor(Client.Client1, capacity);
			const ids: SessionSpaceCompressedId[] = [];
			for (let i = 0; i < capacity; i++) {
				if (i === 1) {
					compressor.finalizeCreationRange(compressor.takeNextCreationRange());
				}
				ids.push(compressor.generateCompressedId(i % 3 === 0 ? undefined : `override${i}`));
			}
			const returnedIds = [...compressor.getAllIdsFromLocalSession()];
			expect(returnedIds).to.deep.equal(ids);
		});
	});

	it('has default attribution ID', () => {
		const compressor = createCompressor(Client.Client1);
		expectDefined(compressor.attributionId);
	});

	it('correctly uses explicit attribution ID', () => {
		const attributionId = generateStableId();
		const compressor = createCompressor(Client.Client1, 5, attributionId);
		expect(compressor.attributionId).to.equal(attributionId);
		const range1 = compressor.takeNextCreationRange();
		expect(compressor.attributionId).to.equal(attributionId);
		expect(range1.attributionId).to.equal(attributionId);
	});

	it('only sends attribution ID until the first ID is allocated', () => {
		const compressor = createCompressor(Client.Client1, 5, generateStableId());
		let range = compressor.takeNextCreationRange();
		expectDefined(range.attributionId);
		range = compressor.takeNextCreationRange();
		expectDefined(range.attributionId);
		compressor.generateCompressedId();
		range = compressor.takeNextCreationRange();
		expectDefined(range.attributionId);
		range = compressor.takeNextCreationRange();
		expect(range.attributionId).to.be.undefined;
	});

	it('does not send default attribution ID', () => {
		const compressor = createCompressor(Client.Client1);
		const range = compressor.takeNextCreationRange();
		expect(range.attributionId).to.be.undefined;
	});

	it('attributes correctly after unification', () => {
		const compressor1 = createCompressor(Client.Client1, undefined, attributionIds.get(Client.Client1));
		const compressor2 = createCompressor(Client.Client2, undefined, attributionIds.get(Client.Client2));
		const id1 = compressor1.generateCompressedId('override');
		const id2 = compressor2.generateCompressedId('override');
		const range1 = compressor1.takeNextCreationRange();
		const range2 = compressor2.takeNextCreationRange();
		compressor1.finalizeCreationRange(range2); // 2 gets sequenced first
		compressor2.finalizeCreationRange(range2);
		compressor1.finalizeCreationRange(range1);
		compressor2.finalizeCreationRange(range1);
		expect(compressor1.normalizeToOpSpace(id1)).to.equal(compressor2.normalizeToOpSpace(id2));
		expect(compressor1.attributeId(id1)).to.equal(attributionIds.get(Client.Client2));
		expect(compressor1.attributeId(compressor1.recompress(compressor2.decompress(id2)))).to.equal(
			attributionIds.get(Client.Client2)
		);
		expect(compressor2.attributeId(compressor2.recompress(compressor1.decompress(id1)))).to.equal(
			attributionIds.get(Client.Client2)
		);
		expect(compressor2.attributeId(id2)).to.equal(attributionIds.get(Client.Client2));
	});

	describe('can produce a creation range', () => {
		const tests: {
			title: string;
			overrideIndices: number[];
			idCount: number;
		}[] = [
			{ title: 'that is empty', overrideIndices: [], idCount: 0 },
			{ title: 'with only sequential IDs', overrideIndices: [], idCount: 3 },
			{
				title: 'with an overriding ID',
				overrideIndices: [0],
				idCount: 1,
			},
			{
				title: 'with a sequential ID before an overriding ID',
				overrideIndices: [1],
				idCount: 2,
			},
			{
				title: 'with a sequential ID after an overriding ID',
				overrideIndices: [0],
				idCount: 2,
			},
			{
				title: 'with an overriding ID between sequential IDs',
				overrideIndices: [1],
				idCount: 3,
			},
			{
				title: 'with a sequential ID between override IDs',
				overrideIndices: [0, 2],
				idCount: 3,
			},
		];

		tests.forEach(({ title, overrideIndices, idCount }) => {
			it(title, () => {
				const compressor = createCompressor(Client.Client1);
				validateIdCreationRange(compressor, idCount, new Set(overrideIndices));
			});

			tests.forEach(({ title: title2, overrideIndices: overrideIndices2, idCount: idCount2 }) => {
				it(`${title2} after a range ${title}`, () => {
					const compressor = createCompressor(Client.Client1);
					const lastTaken = validateIdCreationRange(compressor, idCount, new Set(overrideIndices));
					validateIdCreationRange(compressor, idCount2, new Set(overrideIndices2), lastTaken);
				});
			});
		});

		function validateIdCreationRange(
			compressor: IdCompressor,
			idCount: number,
			overrideIndices: Set<number>,
			lastTakenId = 0 as UnackedLocalId
		): UnackedLocalId {
			const overrides: [SessionSpaceCompressedId, string?][] = [];
			for (let i = 0; i < idCount; i++) {
				const override = overrideIndices.has(i) ? v4() : undefined;
				const id = compressor.generateCompressedId(override);
				overrides.push([id, override]);
			}
			const range = compressor.takeNextCreationRange();
			let newLastTakenId = lastTakenId;
			let idsActual = getIds(range);
			if (overrides.length === 0) {
				expect(idsActual).to.be.undefined;
			} else {
				idsActual = expectDefined(idsActual);
				expect(overrides[0][0]).to.equal(idsActual.first);
				expect(overrides[overrides.length - 1][0]).to.equal(idsActual.last);
				for (const [id, uuid] of Object.entries(overrideIndices)) {
					expect(overrides[id][1]).to.equal(uuid);
				}
				newLastTakenId = idsActual.last;
			}

			return newLastTakenId;
		}
	});

	describe('Finalizing', () => {
		it('can finalize multiple overrides into the same cluster using different ranges', () => {
			const compressor = createCompressor(Client.Client1);
			const override1 = 'override1';
			const override2 = 'override2';
			const id1 = compressor.generateCompressedId(override1);
			compressor.generateCompressedId();
			const range1 = compressor.takeNextCreationRange();
			const id2 = compressor.generateCompressedId(override2);
			const range2 = compressor.takeNextCreationRange();
			compressor.finalizeCreationRange(range1);
			compressor.finalizeCreationRange(range2);
			const finalId1 = compressor.normalizeToOpSpace(id1);
			const finalId2 = compressor.normalizeToOpSpace(id2);
			expect(isFinalId(finalId1)).to.be.true;
			expect(isFinalId(finalId2)).to.be.true;
			expect(compressor.decompress(finalId1)).to.equal(override1);
			expect(compressor.decompress(finalId2)).to.equal(override2);
		});

		it('prevents attempts to finalize ranges twice', () => {
			const rangeCompressor = createCompressor(Client.Client1);
			generateCompressedIds(rangeCompressor, 3);
			const batchRange = rangeCompressor.takeNextCreationRange();
			rangeCompressor.finalizeCreationRange(batchRange);
			assert.throws(
				() => rangeCompressor.finalizeCreationRange(batchRange),
				validateAssertionError('Ranges finalized out of order.')
			);

			// Make a new compressor, as the first one will be left in a bad state
			const explicitCompressor = createCompressor(Client.Client1);
			explicitCompressor.generateCompressedId();
			explicitCompressor.generateCompressedId('override');
			const explicitRange = explicitCompressor.takeNextCreationRange();
			explicitCompressor.finalizeCreationRange(explicitRange);
			assert.throws(
				() => explicitCompressor.finalizeCreationRange(explicitRange),
				validateAssertionError('Ranges finalized out of order.')
			);
		});

		it('prevents attempts to finalize ranges out of order', () => {
			const compressor = createCompressor(Client.Client1);
			compressor.generateCompressedId();
			compressor.takeNextCreationRange();
			compressor.generateCompressedId();
			const secondRange = compressor.takeNextCreationRange();
			assert.throws(
				() => compressor.finalizeCreationRange(secondRange),
				validateAssertionError('Ranges finalized out of order.')
			);
		});

		it('can finalize ranges into clusters of varying sizes', () => {
			for (let i = 1; i < 5; i++) {
				for (let j = 0; j <= i; j++) {
					const compressor = createCompressor(Client.Client1, i);
					const ids = new Set<SessionSpaceCompressedId>();
					for (let k = 0; k <= j; k++) {
						ids.add(compressor.generateCompressedId());
					}
					compressor.finalizeCreationRange(compressor.takeNextCreationRange());
					const opIds = new Set<OpSpaceCompressedId>();
					ids.forEach((id) => opIds.add(compressor.normalizeToOpSpace(id)));
					expect(ids.size).to.equal(opIds.size);
					opIds.forEach((id) => expect(isFinalId(id)).to.be.true);
				}
			}
		});

		it('prevents finalizing unacceptably enormous amounts of ID allocation', () => {
			const compressor1 = createCompressor(Client.Client1);
			const integerLargerThanHalfMax = Math.round((Number.MAX_SAFE_INTEGER / 3) * 2);
			const midPoint = -integerLargerThanHalfMax as UnackedLocalId;
			const largeRange1: IdCreationRange = {
				sessionId: sessionIds.get(Client.Client2),
				ids: { first: -1 as UnackedLocalId, last: midPoint },
			};
			compressor1.finalizeCreationRange(largeRange1);
			const largeRange2: IdCreationRange = {
				sessionId: sessionIds.get(Client.Client2),
				ids: {
					first: (midPoint - 1) as UnackedLocalId,
					last: (-Number.MAX_SAFE_INTEGER - 2) as UnackedLocalId,
				},
			};
			assert.throws(
				() => compressor1.finalizeCreationRange(largeRange2),

				validateAssertionError('The number of allocated final IDs must not exceed the JS maximum safe integer.')
			);
		});
	});

	describe('Compression', () => {
		it('can re-compress a sequential uuid it generated', () => {
			const compressor = createCompressor(Client.Client1);
			const id = compressor.generateCompressedId();
			const uuid = compressor.decompress(id);
			expect(compressor.recompress(uuid)).to.equal(id);
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			expect(compressor.recompress(uuid)).to.equal(id);
		});

		it('can re-compress an override', () => {
			const compressor = createCompressor(Client.Client1);
			const override = 'override';
			const id = compressor.generateCompressedId(override);
			expect(compressor.recompress(override)).to.equal(id);
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			expect(compressor.recompress(override)).to.equal(id);
		});

		it('can re-compress overrides from a remote client it has finalized', () => {
			const compressor = createCompressor(Client.Client1);
			const id = compressor.generateCompressedId();
			const override = 'override';
			compressor.generateCompressedId(override);
			const uuid = compressor.decompress(id);

			const compressor2 = createCompressor(Client.Client2);
			compressor2.finalizeCreationRange(compressor.takeNextCreationRange());
			const finalId1 = compressor2.recompress(uuid);
			const finalId2 = compressor2.recompress(override);
			if (finalId1 === undefined || finalId2 === undefined) {
				expect.fail();
			}
			expect(isFinalId(finalId1)).to.be.true;
			expect(isFinalId(finalId2)).to.be.true;
		});

		it('will not compress an override it never compressed or finalized', () => {
			const compressor = createCompressor(Client.Client1, 5);
			// Leading zeroes to exploit calls to getOrNextLower on uuid maps, as it will be before test session uuids
			const override = 'override';
			expect(compressor.tryRecompress(override)).to.be.undefined;
			expect(compressor.tryRecompress(stableIdFromNumericUuid(sessionNumericUuids.get(Client.Client1), 1))).to.be
				.undefined;
			compressor.generateCompressedId(override);
			generateCompressedIds(compressor, 2);
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			expect(compressor.tryRecompress(stableIdFromNumericUuid(sessionNumericUuids.get(Client.Client1), 4))).to.be
				.undefined;
		});

		it('can re-compress an eagerly generated final ID that is not finalized', () => {
			const compressor = createCompressor(Client.Client1, 5);
			compressor.generateCompressedId();
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			const finalId = compressor.generateCompressedId();
			expect(isFinalId(finalId)).to.be.true;
			const stableId = stableIdFromNumericUuid(numericUuidFromStableId(sessionIds.get(Client.Client1)), 1);
			expect(compressor.recompress(stableId)).to.equal(finalId);
		});
	});

	describe('Decompression', () => {
		it('can decompress a local ID before and after finalizing', () => {
			const compressor = createCompressor(Client.Client1);
			const id = compressor.generateCompressedId();
			const uuid = compressor.decompress(id);
			expect(isStableId(uuid)).to.be.true;
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			expect(compressor.decompress(id)).to.equal(uuid);
		});

		it('can decompress reserved IDs', () => {
			// This is a glass box test in that it increments UUIDs
			const compressor = createCompressor(Client.Client1);
			expect(compressor.decompress(compressor.getReservedId(0))).to.equal(legacySharedTreeInitialTreeId);
			const reservedSessionUuid = numericUuidFromStableId(
				assertIsStableId(compressor.decompress(compressor.getReservedId(1)))
			);
			for (let i = 1; i < compressor.reservedIdCount; i++) {
				const reservedId = compressor.getReservedId(i);
				const stable = compressor.decompress(reservedId);
				expect(stable).to.equal(stableIdFromNumericUuid(incrementUuid(reservedSessionUuid, i - 1)));
				const finalIdForReserved = compressor.recompress(stable);
				expect(isLocalId(finalIdForReserved)).to.be.false;
				expect(finalIdForReserved).to.equal(reservedId);
			}
			const outOfBoundsError = 'Reserved Id index out of bounds';
			assert.throws(() => compressor.getReservedId(-1), validateAssertionError(outOfBoundsError));
			assert.throws(
				() => compressor.getReservedId(compressor.reservedIdCount),
				validateAssertionError(outOfBoundsError)
			);
		});

		it('can decompress a final ID', () => {
			const compressor = createCompressor(Client.Client1);
			const id = compressor.generateCompressedId();
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			const finalId = compressor.normalizeToOpSpace(id);
			if (isLocalId(finalId)) {
				expect.fail('Op space ID was finalized but is local');
			}
			const uuid = compressor.decompress(finalId);
			expect(isStableId(uuid)).to.be.true;
		});

		it('can decompress a final ID with an override', () => {
			const compressor = createCompressor(Client.Client1);
			const override = 'override';
			const id = compressor.generateCompressedId(override);
			const range = compressor.takeNextCreationRange();
			compressor.finalizeCreationRange(range);
			const finalId = compressor.normalizeToOpSpace(id);
			if (isLocalId(finalId)) {
				expect.fail('Op space ID was finalized but is local');
			}
			const uuid = compressor.decompress(finalId);
			expect(uuid).to.equal(override);
		});

		it('can decompress an override that is an UUID', () => {
			const compressor = createCompressor(Client.Client1, 5);
			const uuid = 'd1302ab1-3c08-4e79-a49a-4c39ac369c16';
			const id = compressor.generateCompressedId(uuid);
			expect(compressor.decompress(id)).to.equal(uuid);
		});

		it('properly sorts UUID-like overrides separately from true UUIDs', () => {
			// This is a glass box test that ensures overrides which would sort in between a cluster base UUID and an UUID higher up in the
			// same cluster are not accidentally retrieved during cluster ID lookup.
			const compressor = createCompressor(Client.Client1, 5);
			const override = `${compressor.localSessionId}6`;
			const id = compressor.generateCompressedId();
			compressor.generateCompressedId(override);
			const decompressedId = compressor.decompress(id);
			expect(compressor.recompress(decompressedId)).to.equal(id);
		});

		it('can decompress an override that starts with the reserved prefix character', () => {
			const compressor = createCompressor(Client.Client1, 5);
			const override = `\ue15e${compressor.localSessionId}`;
			const id = compressor.generateCompressedId(override);
			expect(compressor.decompress(id)).to.equal(override);
		});

		it('can decompress an eagerly generated final ID that is not finalized', () => {
			const compressor = createCompressor(Client.Client1, 5);
			compressor.generateCompressedId();
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			const finalId = compressor.generateCompressedId();
			expect(isFinalId(finalId)).to.be.true;
			expect(compressor.decompress(finalId)).to.equal(
				stableIdFromNumericUuid(numericUuidFromStableId(sessionIds.get(Client.Client1)), 1)
			);
		});
	});

	describe('Normalization', () => {
		it('can normalize a local ID to op space before finalizing', () => {
			const compressor = createCompressor(Client.Client1);
			const id = compressor.generateCompressedId();
			const normalized = compressor.normalizeToOpSpace(id);
			expect(isLocalId(id)).to.be.true;
			expect(id).to.equal(normalized);
		});

		it('can normalize a local ID to op space after finalizing', () => {
			const compressor = createCompressor(Client.Client1);
			const id = compressor.generateCompressedId();
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			const normalized = compressor.normalizeToOpSpace(id);
			expect(isFinalId(normalized)).to.be.true;
			expect(id).to.not.equal(normalized);
		});

		it('can normalize an eagerly generated final ID', () => {
			const compressor = createCompressor(Client.Client1, 5);
			compressor.generateCompressedId();
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			const eagerFinalId = compressor.generateCompressedId();
			expect(isFinalId(eagerFinalId)).to.be.true;
			const opNormalized = compressor.normalizeToOpSpace(eagerFinalId);
			expect(eagerFinalId).to.equal(opNormalized);
			const sessionNormalized = compressor.normalizeToSessionSpace(opNormalized, compressor.localSessionId);
			expect(sessionNormalized).to.equal(opNormalized);
		});

		it('cannot normalize a remote ID to session space if it has not been finalized', () => {
			const compressor1 = createCompressor(Client.Client1);
			const compressor2 = createCompressor(Client.Client2);
			const normalized = compressor1.normalizeToOpSpace(compressor1.generateCompressedId());
			assert.throws(
				() => compressor2.normalizeToSessionSpace(normalized, compressor1.localSessionId),
				validateAssertionError('No IDs have ever been finalized by the supplied session.')
			);
		});

		it('can normalize local and final IDs from a remote session to session space', () => {
			const compressor1 = createCompressor(Client.Client1);
			const compressor2 = createCompressor(Client.Client2);
			const id = compressor1.generateCompressedId();
			const normalizedLocal = compressor1.normalizeToOpSpace(id);
			const range = compressor1.takeNextCreationRange();
			compressor1.finalizeCreationRange(range);
			const normalizedFinal = compressor1.normalizeToOpSpace(id);
			compressor2.finalizeCreationRange(range);
			expect(isLocalId(normalizedLocal)).to.be.true;
			expect(isFinalId(normalizedFinal)).to.be.true;
			expect(compressor2.normalizeToSessionSpace(normalizedFinal, compressor1.localSessionId)).to.equal(
				normalizedFinal
			);
			expect(compressor2.normalizeToSessionSpace(normalizedLocal, compressor1.localSessionId)).to.equal(
				normalizedFinal
			);
		});

		it("can normalize a final ID created by the local session but sent in another client's op space", () => {
			// Regression test for the situation in which a client creates a final ID and another client references
			// that final ID in a message back to the creating client. The creating client will normalize it and
			// pass the session ID of the remote (non-creating) client. This should be handled correctly.
			const compressor = createCompressor(Client.Client1, 5);
			const compressor2 = createCompressor(Client.Client2, 5);
			const id = compressor.generateCompressedId();
			const creationRange = compressor.takeNextCreationRange();
			compressor.finalizeCreationRange(creationRange);
			compressor2.finalizeCreationRange(creationRange);
			const idInClient2OpSpace = compressor2.normalizeToOpSpace(
				compressor2.normalizeToSessionSpace(compressor.normalizeToOpSpace(id), compressor.localSessionId)
			);
			const normalizedToClient1SessionSpace = compressor.normalizeToSessionSpace(
				idInClient2OpSpace,
				compressor2.localSessionId
			);
			expect(normalizedToClient1SessionSpace).to.equal(id);
		});
	});

	describe('Telemetry', () => {
		it('emits first cluster and new cluster telemetry events', () => {
			const mockLogger = new MockLogger();
			const compressor = createCompressor(Client.Client1, 5, undefined, mockLogger);
			const localId1 = compressor.generateCompressedId();
			expect(isLocalId(localId1)).to.be.true;
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());

			mockLogger.assertMatch([
				{
					eventName: 'SharedTreeIdCompressor:FirstCluster',
					sessionId: '88888888-8888-4888-b088-888888888888',
				},
				{
					eventName: 'SharedTreeIdCompressor:NewCluster',
					sessionId: '88888888-8888-4888-b088-888888888888',
					clusterCapacity: 5,
					clusterCount: 1,
				},
				{
					eventName: 'SharedTreeIdCompressor:IdCompressorStatus',
					sessionId: '88888888-8888-4888-b088-888888888888',
					eagerFinalIdCount: 0,
					overridesCount: 0,
					localIdCount: 1,
				},
			]);
		});

		it('emits new cluster event on second cluster', () => {
			// Fill the first cluster
			const mockLogger = new MockLogger();
			const compressor = createCompressor(Client.Client1, 5, undefined, mockLogger);
			for (let i = 0; i < 5; i++) {
				compressor.generateCompressedId();
			}
			const range = compressor.takeNextCreationRange();
			compressor.finalizeCreationRange(range);

			// Create another cluster with a different client so that expansion doesn't happen
			const mockLogger2 = new MockLogger();
			const compressor2 = createCompressor(Client.Client2, 5, undefined, mockLogger2);
			compressor2.finalizeCreationRange(range);
			compressor2.generateCompressedId();
			const range2 = compressor2.takeNextCreationRange();
			compressor2.finalizeCreationRange(range2);
			compressor.finalizeCreationRange(range2);
			// Make sure we emitted the FirstCluster event
			mockLogger.assertMatchAny([
				{
					eventName: 'SharedTreeIdCompressor:FirstCluster',
				},
			]);
			mockLogger.clear();

			// Trigger a new cluster creation and make sure FirstCluster isn't emitted
			compressor.generateCompressedId();
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			mockLogger.assertMatchAny([
				{
					eventName: 'SharedTreeIdCompressor:NewCluster',
				},
			]);
			mockLogger.assertMatchNone([
				{
					eventName: 'SharedTreeIdCompressor:FirstCluster',
				},
			]);
		});

		it('correctly logs telemetry events for eager final id allocations', () => {
			const mockLogger = new MockLogger();
			const compressor = createCompressor(Client.Client1, 5, undefined, mockLogger);
			const localId1 = compressor.generateCompressedId();
			expect(isLocalId(localId1)).to.be.true;

			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			mockLogger.assertMatchAny([
				{
					eventName: 'SharedTreeIdCompressor:IdCompressorStatus',
					eagerFinalIdCount: 0,
					localIdCount: 1,
					overridesCount: 0,
					sessionId: '88888888-8888-4888-b088-888888888888',
				},
			]);
			mockLogger.clear();
			const finalId1 = compressor.generateCompressedId();
			const finalId2 = compressor.generateCompressedId();
			expect(isFinalId(finalId1)).to.be.true;
			expect(isFinalId(finalId2)).to.be.true;

			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			mockLogger.assertMatchAny([
				{
					eventName: 'SharedTreeIdCompressor:IdCompressorStatus',
					eagerFinalIdCount: 2,
					localIdCount: 0,
					overridesCount: 0,
					sessionId: '88888888-8888-4888-b088-888888888888',
				},
			]);
		});

		it('correctly logs telemetry events for expansion case', () => {
			const mockLogger = new MockLogger();
			const compressor = createCompressor(Client.Client1, 5, undefined, mockLogger);
			const localId1 = compressor.generateCompressedId();
			expect(isLocalId(localId1)).to.be.true;

			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			mockLogger.assertMatchAny([
				{
					eventName: 'SharedTreeIdCompressor:IdCompressorStatus',
					eagerFinalIdCount: 0,
					localIdCount: 1,
					overridesCount: 0,
					sessionId: '88888888-8888-4888-b088-888888888888',
				},
			]);
			mockLogger.clear();

			for (let i = 0; i < 4; i++) {
				const id = compressor.generateCompressedId();
				expect(isFinalId(id)).to.be.true;
			}

			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			mockLogger.assertMatchAny([
				{
					eventName: 'SharedTreeIdCompressor:IdCompressorStatus',
					eagerFinalIdCount: 4,
					localIdCount: 0,
					overridesCount: 0,
					sessionId: '88888888-8888-4888-b088-888888888888',
				},
			]);
			mockLogger.clear();

			const expansionId1 = compressor.generateCompressedId();
			const expansionId2 = compressor.generateCompressedId();
			expect(isLocalId(expansionId1)).to.be.true;
			expect(isLocalId(expansionId2)).to.be.true;

			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			mockLogger.assertMatch([
				{
					eventName: 'SharedTreeIdCompressor:ClusterExpansion',
					sessionId: '88888888-8888-4888-b088-888888888888',
					previousCapacity: 5,
					newCapacity: 12,
					overflow: 2,
				},
				{
					eventName: 'SharedTreeIdCompressor:IdCompressorStatus',
					eagerFinalIdCount: 2,
					localIdCount: 0,
					overridesCount: 0,
					sessionId: '88888888-8888-4888-b088-888888888888',
				},
			]);
		});

		it('emits correct telemetry status with overrides', () => {
			const mockLogger = new MockLogger();
			const compressor = createCompressor(Client.Client1, 5, undefined, mockLogger);
			const localId1 = compressor.generateCompressedId();
			expect(isLocalId(localId1)).to.be.true;

			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			mockLogger.assertMatchAny([
				{
					eventName: 'SharedTreeIdCompressor:IdCompressorStatus',
					eagerFinalIdCount: 0,
					localIdCount: 1,
					overridesCount: 0,
					sessionId: '88888888-8888-4888-b088-888888888888',
				},
			]);
			mockLogger.clear();

			const finalId2 = compressor.generateCompressedId();
			const overrideId3 = compressor.generateCompressedId('override');
			expect(isFinalId(finalId2)).to.be.true;
			expect(isLocalId(overrideId3)).to.be.true;

			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			mockLogger.assertMatchAny([
				{
					eventName: 'SharedTreeIdCompressor:IdCompressorStatus',
					eagerFinalIdCount: 1,
					localIdCount: 1,
					overridesCount: 1,
					sessionId: '88888888-8888-4888-b088-888888888888',
				},
			]);
		});

		it('emits telemetry when serialized', () => {
			const mockLogger = new MockLogger();
			const compressor = createCompressor(Client.Client1, 5, undefined, mockLogger);
			const localId1 = compressor.generateCompressedId();
			expect(isLocalId(localId1)).to.be.true;

			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			compressor.serialize(false);

			mockLogger.assertMatchAny([
				{
					eventName: 'SharedTreeIdCompressor:SerializedIdCompressorSize',
					size: 137,
					clusterCount: 1,
					sessionCount: 1,
				},
			]);
		});
	});

	describe('Eager final ID allocation', () => {
		it('eagerly allocates final IDs when cluster creation has been finalized', () => {
			const compressor = createCompressor(Client.Client1, 5);
			const localId1 = compressor.generateCompressedId();
			expect(isLocalId(localId1)).to.be.true;
			const localId2 = compressor.generateCompressedId();
			expect(isLocalId(localId2)).to.be.true;
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());
			const finalId3 = compressor.generateCompressedId();
			expect(isFinalId(finalId3)).to.be.true;
			const finalId4 = compressor.generateCompressedId();
			expect(isFinalId(finalId4)).to.be.true;
			const finalId5 = compressor.generateCompressedId();
			expect(isFinalId(finalId5)).to.be.true;
			const localId6 = compressor.generateCompressedId();
			expect(isLocalId(localId6)).to.be.true;

			compressor.finalizeCreationRange(compressor.takeNextCreationRange());

			const opSpaceId1 = compressor.normalizeToOpSpace(localId1);
			const opSpaceId2 = compressor.normalizeToOpSpace(localId2);
			const opSpaceId3 = compressor.normalizeToOpSpace(finalId3);
			const opSpaceId4 = compressor.normalizeToOpSpace(finalId4);
			const opSpaceId5 = compressor.normalizeToOpSpace(finalId5);
			const opSpaceId6 = compressor.normalizeToOpSpace(localId6);

			expectAssert(isFinalId(opSpaceId1));
			expectAssert(isFinalId(opSpaceId2));
			expectAssert(isFinalId(opSpaceId3) && opSpaceId3 === finalId3);
			expectAssert(isFinalId(opSpaceId4) && opSpaceId4 === finalId4);
			expectAssert(isFinalId(opSpaceId5) && opSpaceId5 === finalId5);
			expectAssert(isFinalId(opSpaceId6));

			expect(compressor.normalizeToSessionSpace(opSpaceId1)).to.equal(localId1);
			expect(compressor.normalizeToSessionSpace(opSpaceId2)).to.equal(localId2);
			expect(compressor.normalizeToSessionSpace(opSpaceId3)).to.equal(finalId3);
			expect(compressor.normalizeToSessionSpace(opSpaceId4)).to.equal(finalId4);
			expect(compressor.normalizeToSessionSpace(opSpaceId5)).to.equal(finalId5);
			expect(compressor.normalizeToSessionSpace(opSpaceId6)).to.equal(localId6);
		});

		it('does not eagerly allocate final IDs for IDs with overrides', () => {
			const compressor = createCompressor(Client.Client1, 5);
			const localId1 = compressor.generateCompressedId();
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());

			const override1 = compressor.generateCompressedId('override1');
			expect(isLocalId(override1)).to.be.true;
			const finalId1 = compressor.generateCompressedId();
			expect(isFinalId(finalId1)).to.be.true;

			generateCompressedIds(compressor, 5);
			compressor.finalizeCreationRange(compressor.takeNextCreationRange());

			const override2 = compressor.generateCompressedId('override2');
			expect(isLocalId(override2)).to.be.true;
			const finalId2 = compressor.generateCompressedId();
			expect(isFinalId(finalId2)).to.be.true;

			compressor.finalizeCreationRange(compressor.takeNextCreationRange());

			const opSpaceId1 = compressor.normalizeToOpSpace(localId1);
			const opSpaceId2 = compressor.normalizeToOpSpace(override1);
			const opSpaceId3 = compressor.normalizeToOpSpace(finalId1);
			const opSpaceId4 = compressor.normalizeToOpSpace(override2);
			const opSpaceId5 = compressor.normalizeToOpSpace(finalId2);

			expectAssert(isFinalId(opSpaceId1));
			expectAssert(isFinalId(opSpaceId2));
			expectAssert(isFinalId(opSpaceId3) && opSpaceId3 === finalId1);
			expectAssert(isFinalId(opSpaceId4));
			expectAssert(isFinalId(opSpaceId5) && opSpaceId5 === finalId2);

			expect(compressor.normalizeToSessionSpace(opSpaceId1)).to.equal(localId1);
			expect(compressor.normalizeToSessionSpace(opSpaceId2)).to.equal(override1);
			expect(compressor.normalizeToSessionSpace(opSpaceId3)).to.equal(finalId1);
			expect(compressor.normalizeToSessionSpace(opSpaceId4)).to.equal(override2);
			expect(compressor.normalizeToSessionSpace(opSpaceId5)).to.equal(finalId2);
		});

		it('correctly normalizes eagerly allocated final IDs', () => {
			const compressor = createCompressor(Client.Client1, 5);
			const localId1 = compressor.generateCompressedId();
			const range1 = compressor.takeNextCreationRange();
			const localId2 = compressor.generateCompressedId();
			const range2 = compressor.takeNextCreationRange();
			expect(isLocalId(localId1)).to.be.true;
			expect(isLocalId(localId2)).to.be.true;

			compressor.finalizeCreationRange(range1);
			compressor.finalizeCreationRange(range2);

			const opSpaceId1 = compressor.normalizeToOpSpace(localId1);
			const opSpaceId2 = compressor.normalizeToOpSpace(localId2);

			expectAssert(isFinalId(opSpaceId1));
			expectAssert(isFinalId(opSpaceId2));

			expect(compressor.normalizeToSessionSpace(opSpaceId1)).to.equal(localId1);
			expect(compressor.normalizeToSessionSpace(opSpaceId2)).to.equal(localId2);
		});

		it('generates correct eager finals when there are outstanding locals after cluster expansion', () => {
			const compressor = createCompressor(Client.Client1, 2);

			// Before cluster expansion
			expect(isLocalId(compressor.generateCompressedId())).to.be.true;
			const rangeA = compressor.takeNextCreationRange();
			compressor.finalizeCreationRange(rangeA);
			expect(isFinalId(compressor.generateCompressedId())).to.be.true;

			// After cluster expansion
			expect(isLocalId(compressor.generateCompressedId())).to.be.true;
			const rangeB = compressor.takeNextCreationRange();
			const localId = compressor.generateCompressedId();
			expect(isLocalId(localId)).to.be.true;

			// Take a range that won't be finalized in this test; the finalizing of range B should associate this range with finals
			const rangeC = compressor.takeNextCreationRange();

			compressor.finalizeCreationRange(rangeB);
			const eagerId = compressor.generateCompressedId();
			expect(isFinalId(eagerId)).to.be.true;

			expect(compressor.recompress(compressor.decompress(localId))).to.equal(localId);
			expect(compressor.recompress(compressor.decompress(eagerId))).to.equal(eagerId);

			compressor.finalizeCreationRange(rangeC);

			expect(compressor.recompress(compressor.decompress(localId))).to.equal(localId);
			expect(compressor.recompress(compressor.decompress(eagerId))).to.equal(eagerId);
		});

		it('generates unique eager finals when multiple outstanding creation ranges during finalizing', () => {
			const compressor = createCompressor(Client.Client1, 10 /* must be 10 for the test to make sense */);

			// Make a first outstanding range
			const id1_1 = compressor.generateCompressedId();
			const id1_2 = compressor.generateCompressedId();
			expect(isLocalId(id1_1)).to.be.true;
			expect(isLocalId(id1_2)).to.be.true;
			const range1 = compressor.takeNextCreationRange();

			// Make a second outstanding range
			const id2_1 = compressor.generateCompressedId();
			const id2_2 = compressor.generateCompressedId();
			expect(isLocalId(id2_1)).to.be.true;
			expect(isLocalId(id2_2)).to.be.true;
			const range2 = compressor.takeNextCreationRange();

			// Finalize just the first one, which should create finals that align with both outstanding ranges
			compressor.finalizeCreationRange(range1);

			// Make a third range. This one should be composed of eager finals that align after the two ranges above.
			const id3_1 = compressor.generateCompressedId();
			const id3_2 = compressor.generateCompressedId();
			expect(isFinalId(id3_1)).to.be.true;
			expect(isFinalId(id3_2)).to.be.true;
			const range3 = compressor.takeNextCreationRange();

			// Finalize both initial ranges.
			compressor.finalizeCreationRange(range2);
			compressor.finalizeCreationRange(range3);

			// Make some more eager finals that should be aligned correctly.
			const id4_1 = compressor.generateCompressedId();
			const id4_2 = compressor.generateCompressedId();
			expect(isFinalId(id4_1)).to.be.true;
			expect(isFinalId(id4_2)).to.be.true;

			// Assert everything is unique and consistent.
			const ids = new Set<SessionSpaceCompressedId>();
			const uuids = new Set<StableId | string>();
			[id1_1, id1_2, id2_1, id2_2, id3_1, id3_2, id4_1, id4_2].forEach((id) => {
				ids.add(id);
				uuids.add(compressor.decompress(id));
			});
			expect(ids.size).to.equal(8);
			expect(uuids.size).to.equal(8);
		});

		it('generates unique eager finals when there are still outstanding locals after a cluster is expanded', () => {
			// const compressor = createCompressor(Client.Client1, 4 /* must be 4 for the test to make sense */);

			const compressor = new IdCompressor(sessionIds.get(Client.Client1), 0);
			compressor.clusterCapacity = 4;

			// Make locals to fill half the future cluster
			const id1_1 = compressor.generateCompressedId();
			const id1_2 = compressor.generateCompressedId();
			expect(isLocalId(id1_1)).to.be.true;
			expect(isLocalId(id1_2)).to.be.true;
			const range1 = compressor.takeNextCreationRange();

			// Make locals to overflow the future cluster
			const id2_1 = compressor.generateCompressedId();
			const id2_2 = compressor.generateCompressedId();
			const id2_3 = compressor.generateCompressedId();
			expect(isLocalId(id2_1)).to.be.true;
			expect(isLocalId(id2_2)).to.be.true;
			expect(isLocalId(id2_3)).to.be.true;
			const range2 = compressor.takeNextCreationRange();

			// Finalize the first range. This should align the first four locals (i.e. all of range1, and 2/3 of range2)
			compressor.finalizeCreationRange(range1);

			// Make a single range that should still be overflowing the initial cluster (i.e. be local)
			const id3_1 = compressor.generateCompressedId();
			expect(isLocalId(id3_1)).to.be.true;
			const range3 = compressor.takeNextCreationRange();

			// First finalize should expand the cluster and align all outstanding ranges.
			compressor.finalizeCreationRange(range2);

			// All generated IDs should have aligned finals (even though range3 has not been finalized)
			const allIds = [id1_1, id1_2, id2_1, id2_2, id2_3, id3_1];
			allIds.forEach((id) => expect(isFinalId(compressor.normalizeToOpSpace(id))).to.be.true);

			compressor.finalizeCreationRange(range3);

			// Make one eager final
			const id4_1 = compressor.generateCompressedId();
			allIds.push(id4_1);
			expect(isFinalId(id4_1)).to.be.true;

			// Assert everything is unique and consistent.
			const ids = new Set<SessionSpaceCompressedId>();
			const uuids = new Set<StableId | string>();
			allIds.forEach((id) => {
				ids.add(id);
				uuids.add(compressor.decompress(id));
			});
			expect(ids.size).to.equal(7);
			expect(uuids.size).to.equal(7);
		});
	});

	describe('Serialization', () => {
		it('can serialize an empty compressor', () => {
			const compressor = createCompressor(Client.Client1);
			const [serializedNoSession, serializedWithSession] = expectSerializes(compressor);
			expect(serializedWithSession.clusters.length).to.equal(0, 'reserved cluster should not be serialized');
			expect(serializedNoSession.clusters.length).to.equal(0, 'reserved cluster should not be serialized');
		});

		it('correctly deserializes and resumes a session', () => {
			const compressor1 = createCompressor(Client.Client1, undefined, attributionIds.get(Client.Client1));
			const compressor2 = createCompressor(Client.Client2, undefined, attributionIds.get(Client.Client2));
			compressor1.generateCompressedId();
			const creationRange = compressor1.takeNextCreationRange();
			compressor1.finalizeCreationRange(creationRange);
			compressor2.finalizeCreationRange(creationRange);
			const [_, serializedWithSession] = expectSerializes(compressor1);
			const compressorResumed = IdCompressor.deserialize(serializedWithSession);
			compressorResumed.generateCompressedId();
			const range2 = compressorResumed.takeNextCreationRange();
			compressor1.finalizeCreationRange(range2);
			compressor2.finalizeCreationRange(range2);
			expect(
				IdCompressor.deserialize(compressor1.serialize(false), createSessionId()).equals(
					IdCompressor.deserialize(compressor2.serialize(false), createSessionId()),
					false // don't compare local state
				)
			).to.be.true;
		});

		it('can serialize local state with attribution but no IDs', () => {
			// This is a regression test for the scenario in which an ID compressor sends its first range, which
			// includes its attribution ID, but has made no IDs. An incorrect optimization when serializing had
			// omitted local state if no IDs had been allocated, but then also dropped the `sentAttribution` flag
			const compressor = createCompressor(Client.Client1, undefined, attributionIds.get(Client.Client1));
			const range = compressor.takeNextCreationRange();
			expect(range.ids).to.be.undefined;
			expect(range.attributionId).to.equal(attributionIds.get(Client.Client1));
			expectSerializes(compressor);
		});
	});

	// No validation, as these leave the network in a broken state
	describeNetworkNoValidation('detects UUID collision', (itNetwork) => {
		itNetwork(
			'when a client requests an override that is an UUID reserved for later allocation by a cluster',
			2,
			(network) => {
				network.allocateAndSendIds(Client.Client2, 1);
				network.deliverOperations(Client.Client1);
				const compressor2 = network.getCompressor(Client.Client2);
				const id = network.getIdLog(Client.Client2)[0].id;
				const uuid = assertIsStableId(compressor2.decompress(id));
				const nextUuid = stableIdFromNumericUuid(numericUuidFromStableId(uuid), 1);
				// TODO:#283: Re-assess test when full unification is implemented
				network.allocateAndSendIds(Client.Client1, 1, { 0: nextUuid });
			}
		);

		itNetwork('when a new cluster is allocated whose base UUID collides with an existing override', 2, (network) => {
			network.allocateAndSendIds(Client.Client1, 1);
			network.deliverOperations(DestinationClient.All);
			const compressor1 = network.getCompressor(Client.Client1);
			const id = network.getIdLog(Client.Client1)[0].id;
			const uuid = assertIsStableId(compressor1.decompress(id));
			const nextUuid = stableIdFromNumericUuid(numericUuidFromStableId(uuid), 2);
			network.allocateAndSendIds(Client.Client1, 1, { 0: nextUuid });
			network.allocateAndSendIds(Client.Client2, 1);
			network.deliverOperations(DestinationClient.All);
			network.allocateAndSendIds(Client.Client1, 1); // new cluster
			assert.throws(
				() => network.deliverOperations(Client.Client1),
				validateAssertionError(`Override '${nextUuid}' collides with another allocated UUID.`)
			);
		});

		itNetwork('detects colliding override UUIDs when expanding a cluster', 1, (network) => {
			// This is a glass box test in that it is testing cluster expansion
			network.allocateAndSendIds(Client.Client1, 1);
			network.deliverOperations(DestinationClient.All);
			const compressor1 = network.getCompressor(Client.Client1);
			const id = network.getIdLog(Client.Client1)[0].id;
			const uuid = assertIsStableId(compressor1.decompress(id));
			const expansion = 3;
			const nextUuid = stableIdFromNumericUuid(numericUuidFromStableId(uuid), expansion);
			network.allocateAndSendIds(Client.Client1, expansion, { 0: nextUuid });
			assert.throws(
				() => network.deliverOperations(DestinationClient.All),
				validateAssertionError(`Override '${nextUuid}' collides with another allocated UUID.`)
			);
		});
	});

	describeNetwork('Networked', (itNetwork) => {
		describe('can attribute', () => {
			itNetwork('local IDs before and after being finalized', (network) => {
				const compressor = network.getCompressor(Client.Client1);
				network.allocateAndSendIds(Client.Client1, 1);
				const id = network.getIdLog(Client.Client1)[0].id;
				expect(compressor.attributeId(id)).to.equal(attributionIds.get(Client.Client1));
				network.deliverOperations(Client.Client1);
				expect(compressor.attributeId(id)).to.equal(attributionIds.get(Client.Client1));
			});

			itNetwork('final IDs from a remote session', (network) => {
				const compressor = network.getCompressor(Client.Client1);
				network.allocateAndSendIds(Client.Client2, 1);
				network.deliverOperations(DestinationClient.All);
				const id = network.getSequencedIdLog(Client.Client1)[0].id;
				expect(compressor.attributeId(id)).to.equal(attributionIds.get(Client.Client2));
			});

			itNetwork('final IDs from multiple remote sessions', 1, (network) => {
				const compressor = network.getCompressor(Client.Client1);
				// Ensure multiple clusters are made by each client. Cluster size === 1.
				network.allocateAndSendIds(Client.Client1, compressor.clusterCapacity);
				network.allocateAndSendIds(Client.Client2, compressor.clusterCapacity);
				network.allocateAndSendIds(Client.Client3, compressor.clusterCapacity);
				network.allocateAndSendIds(Client.Client1, compressor.clusterCapacity);
				network.allocateAndSendIds(Client.Client2, compressor.clusterCapacity);
				network.allocateAndSendIds(Client.Client3, compressor.clusterCapacity);
				network.deliverOperations(DestinationClient.All);
				const log = network.getSequencedIdLog(Client.Client1);
				expect(compressor.attributeId(log[0].id)).to.equal(attributionIds.get(Client.Client1));
				expect(compressor.attributeId(log[1].id)).to.equal(attributionIds.get(Client.Client2));
				expect(compressor.attributeId(log[2].id)).to.equal(attributionIds.get(Client.Client3));
				expect(compressor.attributeId(log[3].id)).to.equal(attributionIds.get(Client.Client1));
				expect(compressor.attributeId(log[4].id)).to.equal(attributionIds.get(Client.Client2));
				expect(compressor.attributeId(log[5].id)).to.equal(attributionIds.get(Client.Client3));
			});

			itNetwork('unified IDs', (network) => {
				const override = 'override';
				const allTargets = network.getTargetCompressors(DestinationClient.All);
				for (const [client, compressor] of allTargets) {
					network.allocateAndSendIds(client, 1, { 0: override });
					for (const { id } of network.getIdLog(client)) {
						expect(compressor.attributeId(id)).to.equal(attributionIds.get(client));
					}
				}
				network.deliverOperations(DestinationClient.All);
				const firstTarget = allTargets[0][0];
				for (const [client, compressor] of allTargets) {
					for (const { id } of network.getIdLog(client)) {
						expect(compressor.attributeId(id)).to.equal(attributionIds.get(firstTarget));
					}
				}
			});

			itNetwork('eagerly generated final IDs that are not finalized', (network) => {
				const compressor = network.getCompressor(Client.Client1);
				network.allocateAndSendIds(Client.Client1, 1);
				network.deliverOperations(DestinationClient.All);
				const ids = network.allocateAndSendIds(Client.Client1, 1);
				const id = compressor.normalizeToSessionSpace(ids[0], compressor.localSessionId);
				expect(compressor.attributeId(id)).to.equal(attributionIds.get(Client.Client1));
			});
		});

		itNetwork('upholds the invariant that IDs always decompress to the same UUID', 2, (network) => {
			network.allocateAndSendIds(Client.Client1, 5, {
				1: 'override1',
			});
			network.allocateAndSendIds(Client.Client2, 5, {
				2: 'override2',
			});
			network.allocateAndSendIds(Client.Client3, 5, {
				3: 'override3',
			});

			const preAckLocals = new Map<Client, [SessionSpaceCompressedId, string][]>();
			for (const [client, compressor] of network.getTargetCompressors(MetaClient.All)) {
				const locals: [SessionSpaceCompressedId, string][] = [];
				for (const idData of network.getIdLog(client)) {
					locals.push([idData.id, compressor.decompress(idData.id)]);
				}
				preAckLocals.set(client, locals);
			}

			// Ack all IDs
			network.deliverOperations(DestinationClient.All);

			for (const [client, compressor] of network.getTargetCompressors(MetaClient.All)) {
				const preAckLocalIds = preAckLocals.get(client) ?? fail();
				let i = 0;
				for (const idData of network.getIdLog(client)) {
					if (idData.originatingClient === client) {
						expect(isFinalId(idData.id)).to.be.false;
						const currentUuid = compressor.decompress(idData.id);
						expect(currentUuid).to.equal(preAckLocalIds[i % preAckLocalIds.length][1]);
						i++;
					}
				}
			}
		});

		itNetwork('can normalize session space IDs to op space', 5, (network) => {
			const clusterCapacity = 5;
			const idCount = clusterCapacity * 2;
			for (let i = 0; i < idCount; i++) {
				network.allocateAndSendIds(Client.Client1, 1);
				network.allocateAndSendIds(Client.Client2, 1);
				network.allocateAndSendIds(Client.Client3, 1);
			}

			for (const [client, compressor] of network.getTargetCompressors(MetaClient.All)) {
				for (const idData of network.getIdLog(client)) {
					expect(idData.originatingClient).to.equal(client);
					expect(isLocalId(compressor.normalizeToOpSpace(idData.id))).to.be.true;
				}
			}

			network.deliverOperations(DestinationClient.All);

			for (const [client, compressor] of network.getTargetCompressors(MetaClient.All)) {
				for (const idData of network.getIdLog(client)) {
					expect(isFinalId(compressor.normalizeToOpSpace(idData.id))).to.be.true;
				}
			}
		});

		itNetwork('can normalize local op space IDs from a local session to session space IDs', (network) => {
			const compressor = network.getCompressor(Client.Client1);
			network.allocateAndSendIds(Client.Client1, 1);
			network.deliverOperations(Client.Client1);
			const sessionSpaceIds = network.getIdLog(Client.Client1);
			const opSpaceId = compressor.normalizeToOpSpace(sessionSpaceIds[0].id);
			const sessionSpaceId = compressor.normalizeToSessionSpace(opSpaceId, compressor.localSessionId);
			expect(isFinalId(opSpaceId)).to.be.true;
			expect(isLocalId(sessionSpaceId)).to.be.true;
		});

		itNetwork('can normalize local op space IDs from a remote session to session space IDs', (network) => {
			const compressor1 = network.getCompressor(Client.Client1);
			const compressor2 = network.getCompressor(Client.Client2);
			const opSpaceIds = network.allocateAndSendIds(Client.Client1, 1);
			// Mimic sending a reference to an ID that hasn't been acked yet, such as in a slow network
			const id = opSpaceIds[0];
			const getSessionNormalizedId = () => compressor2.normalizeToSessionSpace(id, compressor1.localSessionId);
			assert.throws(
				getSessionNormalizedId,
				validateAssertionError('No IDs have ever been finalized by the supplied session.')
			);
			network.deliverOperations(Client.Client2);
			expect(isFinalId(getSessionNormalizedId())).to.be.true;
		});

		itNetwork('unifies duplicate overrides', 3, (network) => {
			const override = 'override';
			const compressor1 = network.getCompressor(Client.Client1);
			const compressor2 = network.getCompressor(Client.Client2);
			const compressor3 = network.getCompressor(Client.Client3);
			const clusterCapacity = compressor1.clusterCapacity;

			// Ensure some clusters exist to avoid simple case of empty clusters
			network.allocateAndSendIds(Client.Client1, clusterCapacity);
			network.allocateAndSendIds(Client.Client2, clusterCapacity);
			network.allocateAndSendIds(Client.Client3, clusterCapacity);
			network.deliverOperations(DestinationClient.All);

			const range1 = network.allocateAndSendIds(Client.Client1, 1, { 0: override });
			const overrides1 = expectDefined(getIds(range1)?.overrides);
			const id1 = compressor1.normalizeToSessionSpace(overrides1[0][0], compressor1.localSessionId);
			const opNormalizedLocal1 = compressor1.normalizeToOpSpace(id1);
			expect(isLocalId(opNormalizedLocal1)).to.be.true;
			expect(isFinalId(id1)).to.be.false;

			network.deliverOperations(DestinationClient.Client1);

			const finalId1 = compressor1.normalizeToOpSpace(id1);
			expect(isFinalId(finalId1)).to.be.true;

			const range2 = network.allocateAndSendIds(Client.Client2, 2, { 1: override });
			const overrides2 = expectDefined(getIds(range2)?.overrides);
			const id2 = compressor2.normalizeToSessionSpace(overrides2[0][0], compressor2.localSessionId);
			const opNormalizedLocal2 = compressor2.normalizeToOpSpace(id2);
			expect(isLocalId(opNormalizedLocal2)).to.be.true;
			expect(isFinalId(id2)).to.be.false;

			network.allocateAndSendIds(Client.Client3, 1);
			network.deliverOperations(DestinationClient.All);

			const finalId2 = compressor2.normalizeToOpSpace(id2);
			expect(isFinalId(finalId2)).to.be.true;

			expect(finalId1).to.equal(finalId2);

			expect(compressor1.normalizeToOpSpace(id1)).to.equal(finalId1);
			expect(compressor1.normalizeToSessionSpace(finalId1, compressor1.localSessionId)).to.equal(id1);
			expect(compressor1.normalizeToSessionSpace(opNormalizedLocal2, compressor2.localSessionId)).to.equal(id1);
			expect(compressor1.decompress(id1)).to.equal(override);
			expect(compressor1.decompress(finalId1)).to.equal(override);
			expect(compressor1.recompress(override)).to.equal(id1);

			expect(compressor2.normalizeToOpSpace(id2)).to.equal(finalId2);
			expect(compressor2.normalizeToSessionSpace(finalId1, compressor1.localSessionId)).to.equal(id2);
			expect(compressor2.normalizeToSessionSpace(opNormalizedLocal1, compressor1.localSessionId)).to.equal(id2);
			expect(compressor2.decompress(id2)).to.equal(override);
			expect(compressor2.decompress(finalId2)).to.equal(override);
			expect(compressor2.tryRecompress(override)).to.equal(id2);

			expect(compressor3.normalizeToSessionSpace(finalId1, compressor1.localSessionId)).to.equal(finalId1);
			expect(compressor3.normalizeToSessionSpace(opNormalizedLocal1, compressor1.localSessionId)).to.equal(finalId1);
			expect(compressor3.normalizeToSessionSpace(opNormalizedLocal2, compressor2.localSessionId)).to.equal(finalId1);
			expect(compressor3.decompress(finalId1)).to.equal(override);
			expect(compressor3.recompress(override)).to.equal(finalId1);
		});

		itNetwork('maintains alignment after unifying duplicate overrides', 3, (network) => {
			const override = 'override';
			network.allocateAndSendIds(Client.Client1, 1, { 0: override });
			network.allocateAndSendIds(Client.Client2, 2, { 1: override });
			network.allocateAndSendIds(Client.Client1, 5);
			network.allocateAndSendIds(Client.Client2, 5);
			expectSequencedLogsAlign(network, Client.Client1, Client.Client2, 1);
		});

		function expectSequencedLogsAlign(
			network: IdCompressorTestNetwork,
			client1: Client,
			client2: Client,
			numUnifications = 0
		): void {
			network.deliverOperations(DestinationClient.All);
			assert(client1 !== client2);
			const log1 = network.getSequencedIdLog(client1);
			const log2 = network.getSequencedIdLog(client2);
			expect(log1.length).to.equal(log2.length);
			const compressor1 = network.getCompressor(client1);
			const compressor2 = network.getCompressor(client2);
			const ids = new Set<OpSpaceCompressedId>();
			const uuidsOrOverrides = new Set<string>();
			for (let i = 0; i < log1.length; i++) {
				const data1 = log1[i];
				const id1 = compressor1.normalizeToOpSpace(data1.id);
				const id2 = compressor2.normalizeToOpSpace(log2[i].id);
				expect(isFinalId(id1)).to.be.true;
				ids.add(id1);
				expect(id1).to.equal(id2);
				const uuidOrOverride1 = compressor1.decompress(id1);
				uuidsOrOverrides.add(uuidOrOverride1);
				if (data1.expectedOverride === undefined) {
					expect(isStableId(uuidOrOverride1)).to.be.true;
				}
				expect(uuidOrOverride1).to.equal(compressor2.decompress(id2));
			}
			const expectedSize = log1.length - numUnifications;
			expect(ids.size).to.equal(expectedSize);
			expect(uuidsOrOverrides.size).to.equal(expectedSize);
		}

		itNetwork('produces ID spaces correctly', (network) => {
			// This test asserts that IDs returned from IDCompressor APIs are correctly encoded as either local or final.
			// This is a glass box test in that it assumes the negative/positive encoding of CompressedIds (negative = local, positive = final).
			const compressor1 = network.getCompressor(Client.Client1);

			// Client 1 makes two IDs, two explicit (one with an override) and one sequential
			network.allocateAndSendIds(Client.Client1, 3, {
				1: 'override1',
			});

			network.getIdLog(Client.Client1).forEach((id) => expect(id.id).to.be.lessThan(0));

			// Client 1's IDs have not been acked so have no op space equivalent
			network
				.getIdLog(Client.Client1)
				.forEach((idData) => expect(compressor1.normalizeToOpSpace(idData.id)).to.be.lessThan(0));

			// Client 1's IDs are acked
			network.deliverOperations(Client.Client1);
			network.getIdLog(Client.Client1).forEach((id) => expect(id.id).to.be.lessThan(0));

			// Client 3 makes two IDs, two explicit (one with an override) and one sequential
			network.allocateAndSendIds(Client.Client2, 3, {
				1: 'override2',
			});

			network.getIdLog(Client.Client2).forEach((id) => expect(id.id).to.be.lessThan(0));

			// Client 1 receives Client 2's IDs
			network.deliverOperations(Client.Client1);

			network
				.getIdLog(Client.Client1)
				.slice(-3)
				.forEach((id) => expect(id.id).to.be.greaterThan(0));

			// All IDs have been acked or are from another client, and therefore have a final form in op space
			network
				.getIdLog(Client.Client1)
				.forEach((idData) => expect(compressor1.normalizeToOpSpace(idData.id)).to.be.greaterThan(0));

			// Compression should preserve ID space correctness
			network.getIdLog(Client.Client1).forEach((idData) => {
				const roundtripped = compressor1.recompress(compressor1.decompress(idData.id));
				expect(Math.sign(roundtripped)).to.equal(Math.sign(idData.id));
			});

			network.getIdLog(Client.Client1).forEach((idData) => {
				const opNormalized = compressor1.normalizeToOpSpace(idData.id);
				expect(Math.sign(compressor1.normalizeToSessionSpace(opNormalized, idData.sessionId))).to.equal(
					Math.sign(idData.id)
				);
			});
		});

		itNetwork('produces consistent IDs with large fuzz input', (network) => {
			const generator = take(2000, makeOpGenerator({ includeOverrides: true }));
			performFuzzActions(generator, network, 1984, undefined, true, (network) => network.assertNetworkState());
			network.deliverOperations(DestinationClient.All);
		});

		itNetwork('can set the cluster size via constructor', 2, (network) => {
			const compressor = network.getCompressor(Client.Client1);
			const compressor2 = network.getCompressor(Client.Client2);
			network.allocateAndSendIds(Client.Client1, 1);
			const opSpaceIds = network.allocateAndSendIds(Client.Client2, 2);
			network.deliverOperations(DestinationClient.All);
			// Glass box test, as it knows the order of final IDs
			expect(compressor.normalizeToSessionSpace(opSpaceIds[0], compressor2.localSessionId)).to.equal(
				compressor.reservedIdCount + compressor.clusterCapacity
			);
		});

		itNetwork('can set the cluster size via API', 2, (network) => {
			const compressor = network.getCompressor(Client.Client1);
			const compressor2 = network.getCompressor(Client.Client2);
			const initialClusterCapacity = compressor.clusterCapacity;
			network.allocateAndSendIds(Client.Client1, initialClusterCapacity);
			network.allocateAndSendIds(Client.Client2, initialClusterCapacity);
			network.enqueueCapacityChange(5);
			network.allocateAndSendIds(Client.Client1, 1);
			const opSpaceIds = network.allocateAndSendIds(Client.Client2, 1);
			network.deliverOperations(DestinationClient.All);
			// Glass box test, as it knows the order of final IDs
			expect(compressor.normalizeToSessionSpace(opSpaceIds[0], compressor2.localSessionId)).to.equal(
				compressor.reservedIdCount + initialClusterCapacity * 2 + compressor.clusterCapacity
			);
		});

		itNetwork('does not decompress ids for empty parts of clusters', 2, (network) => {
			// This is a glass box test in that it creates a final ID outside of the ID compressor
			network.allocateAndSendIds(Client.Client1, 1);
			network.deliverOperations(DestinationClient.All);
			const id = network.getSequencedIdLog(Client.Client2)[0].id;
			expect(isFinalId(id)).to.be.true;
			const emptyId = (id + 1) as FinalCompressedId;
			assert.throws(
				() => network.getCompressor(Client.Client2).decompress(emptyId),
				validateAssertionError('Compressed ID was not generated by this compressor')
			);
		});

		describe('Finalizing', () => {
			itNetwork('can finalize IDs from multiple clients', (network) => {
				network.allocateAndSendIds(Client.Client1, 3, {
					1: 'override1',
				});
				network.allocateAndSendIds(Client.Client2, 3, {
					1: 'override2',
				});
				expectSequencedLogsAlign(network, Client.Client1, Client.Client2);
			});

			itNetwork('can finalize a range when the current cluster is full', 5, (network) => {
				const clusterCapacity = network.getCompressor(Client.Client1).clusterCapacity;
				network.allocateAndSendIds(Client.Client1, clusterCapacity);
				network.allocateAndSendIds(Client.Client2, clusterCapacity);
				network.allocateAndSendIds(Client.Client1, clusterCapacity, {
					0: 'override1',
					1: 'override2',
					2: 'override3',
				});
				expectSequencedLogsAlign(network, Client.Client1, Client.Client2);
			});

			itNetwork('can finalize a range that spans multiple clusters', 5, (network) => {
				const clusterCapacity = network.getCompressor(Client.Client1).clusterCapacity;
				network.allocateAndSendIds(Client.Client1, clusterCapacity - 2, {
					0: 'override1',
					1: 'override2',
				});
				network.allocateAndSendIds(Client.Client2, 1);
				network.allocateAndSendIds(Client.Client1, clusterCapacity, {
					0: 'override3',
					1: 'override4',
					2: 'override5',
				});
				expectSequencedLogsAlign(network, Client.Client1, Client.Client2);
			});
		});

		describe('Serialization', () => {
			itNetwork('prevents attempts to resume a session from a serialized compressor with no session', (network) => {
				const compressor = network.getCompressor(Client.Client1);
				network.allocateAndSendIds(Client.Client2, 1);
				network.allocateAndSendIds(Client.Client3, 1);
				network.deliverOperations(Client.Client1);
				const serializedWithoutLocalState = compressor.serialize(false);
				assert.throws(
					() => IdCompressor.deserialize(serializedWithoutLocalState, sessionIds.get(Client.Client2)),
					validateAssertionError('Cannot resume existing session.')
				);
			});

			itNetwork('round-trips local state', 3, (network) => {
				network.allocateAndSendIds(Client.Client1, 2);
				network.allocateAndSendIds(Client.Client2, 3);
				network.allocateAndSendIds(Client.Client1, 5);
				network.allocateAndSendIds(Client.Client1, 5);
				network.allocateAndSendIds(Client.Client3, 3);
				network.allocateAndSendIds(Client.Client2, 3);
				network.deliverOperations(Client.Client1);
				// Some un-acked locals at the end
				network.allocateAndSendIds(Client.Client1, 4);
				const [serializedNoSession, serializedWithSession] = expectSerializes(network.getCompressor(Client.Client1));
				expect(hasOngoingSession(serializedWithSession)).to.be.true;
				expect(hasOngoingSession(serializedNoSession)).to.be.false;
			});

			itNetwork('can serialize a partially empty cluster', 5, (network) => {
				network.allocateAndSendIds(Client.Client1, 2);
				network.deliverOperations(DestinationClient.All);
				expectSerializes(network.getCompressor(Client.Client1));
				expectSerializes(network.getCompressor(Client.Client3));
			});

			itNetwork('can serialize a full cluster', 2, (network) => {
				network.allocateAndSendIds(Client.Client1, 2);
				network.deliverOperations(DestinationClient.All);
				expectSerializes(network.getCompressor(Client.Client1));
				expectSerializes(network.getCompressor(Client.Client3));
			});

			itNetwork('can serialize full clusters from different clients', 2, (network) => {
				network.allocateAndSendIds(Client.Client1, 2);
				network.allocateAndSendIds(Client.Client2, 2);
				network.deliverOperations(DestinationClient.All);
				expectSerializes(network.getCompressor(Client.Client1));
				expectSerializes(network.getCompressor(Client.Client3));
			});

			itNetwork('can serialize clusters of different sizes and clients', 3, (network) => {
				network.allocateAndSendIds(Client.Client1, 2);
				network.allocateAndSendIds(Client.Client2, 3);
				network.allocateAndSendIds(Client.Client1, 5);
				network.allocateAndSendIds(Client.Client1, 5);
				network.allocateAndSendIds(Client.Client2, 3);
				network.deliverOperations(DestinationClient.All);
				expectSerializes(network.getCompressor(Client.Client1));
				expectSerializes(network.getCompressor(Client.Client3));
			});

			itNetwork('can serialize clusters with overrides', 3, (network) => {
				network.allocateAndSendIds(Client.Client1, 2, {
					1: 'override',
				});
				network.allocateAndSendIds(Client.Client2, 3, {
					0: 'override1',
					2: 'override2',
				});
				network.deliverOperations(DestinationClient.All);
				expectSerializes(network.getCompressor(Client.Client1));
				expectSerializes(network.getCompressor(Client.Client3));
			});

			itNetwork('packs IDs into a single cluster when a single client generates non-overridden ids', 3, (network) => {
				network.allocateAndSendIds(Client.Client1, 20);
				network.deliverOperations(DestinationClient.All);
				const [serialized1WithNoSession, serialized1WithSession] = expectSerializes(
					network.getCompressor(Client.Client1)
				);
				expect(serialized1WithNoSession.clusters.length).to.equal(1);
				expect(serialized1WithSession.clusters.length).to.equal(1);
				const [serialized3WithNoSession, serialized3WithSession] = expectSerializes(
					network.getCompressor(Client.Client3)
				);
				expect(serialized3WithNoSession.clusters.length).to.equal(1);
				expect(serialized3WithSession.clusters.length).to.equal(1);
			});

			itNetwork('serializes correctly after unifying duplicate overrides', 3, (network) => {
				const override = 'override';
				network.allocateAndSendIds(Client.Client1, 1, { 0: override });
				network.allocateAndSendIds(Client.Client2, 2, { 1: override });
				network.allocateAndSendIds(Client.Client1, 5);
				network.allocateAndSendIds(Client.Client2, 5);
				network.deliverOperations(DestinationClient.All);
				expectSerializes(network.getCompressor(Client.Client1));
				expectSerializes(network.getCompressor(Client.Client2));
				expectSerializes(network.getCompressor(Client.Client3));
			});

			itNetwork('can resume a session and interact with multiple other clients', 3, (network) => {
				const clusterSize = network.getCompressor(Client.Client1).clusterCapacity;
				network.allocateAndSendIds(Client.Client1, clusterSize);
				network.allocateAndSendIds(Client.Client2, clusterSize);
				network.allocateAndSendIds(Client.Client3, clusterSize);
				network.allocateAndSendIds(Client.Client1, clusterSize);
				network.allocateAndSendIds(Client.Client2, clusterSize);
				network.allocateAndSendIds(Client.Client3, clusterSize);
				network.deliverOperations(DestinationClient.All);
				network.goOfflineThenResume(Client.Client1);
				network.allocateAndSendIds(Client.Client1, 2);
				network.allocateAndSendIds(Client.Client2, 2);
				network.allocateAndSendIds(Client.Client3, 2);
				expectSequencedLogsAlign(network, Client.Client1, Client.Client2);
			});

			itNetwork('can serialize after a large fuzz input', 3, (network) => {
				const generator = take(2000, makeOpGenerator({ includeOverrides: true }));
				performFuzzActions(generator, network, Math.PI, undefined, true, (network) => {
					// Periodically check that everyone in the network has the same serialized state
					network.deliverOperations(DestinationClient.All);
					const compressors = network.getTargetCompressors(DestinationClient.All);
					let deserializedPrev = roundtrip(compressors[0][1], false)[1];
					for (let i = 1; i < compressors.length; i++) {
						const deserializedCur = roundtrip(compressors[i][1], false)[1];
						expect(deserializedPrev.equals(deserializedCur, false)).to.be.true;
						deserializedPrev = deserializedCur;
					}
				});
				expectSerializes(network.getCompressor(Client.Client1));
				expectSerializes(network.getCompressor(Client.Client2));
				expectSerializes(network.getCompressor(Client.Client3));
			});

			itNetwork('stores override indices relative to their clusters', 3, (network) => {
				network.allocateAndSendIds(Client.Client1, 3, { 0: 'cluster1' });
				network.allocateAndSendIds(Client.Client2, 3, { 0: 'cluster2' });
				network.deliverOperations(Client.Client1);
				const serialized = network.getCompressor(Client.Client1).serialize(false);
				expect(serialized.clusters.length).to.equal(2);
				expect(serialized.clusters[0][2]?.[0][0]).to.equal(0);
				expect(serialized.clusters[1][2]?.[0][0]).to.equal(0);
			});
		});
	});
});

type NetworkTestFunction = (title: string, test: (network: IdCompressorTestNetwork) => void) => void;

type NetworkTestFunctionWithCapacity = (
	title: string,
	initialClusterCapacity: number,
	test: (network: IdCompressorTestNetwork) => void
) => void;

function createNetworkTestFunction(validateAfter: boolean): NetworkTestFunction & NetworkTestFunctionWithCapacity {
	return (
		title: string,
		testOrCapacity: ((network: IdCompressorTestNetwork) => void) | number,
		test?: (network: IdCompressorTestNetwork) => void
	) => {
		it(title, () => {
			const hasCapacity = typeof testOrCapacity === 'number';
			const capacity = hasCapacity ? testOrCapacity : undefined;
			const network = new IdCompressorTestNetwork(capacity);
			(hasCapacity ? assertNotUndefined(test) : testOrCapacity)(network);
			if (validateAfter) {
				network.deliverOperations(DestinationClient.All);
				network.assertNetworkState();
			}
		}).timeout(10000);
	};
}

function describeNetwork(title: string, its: (itFunc: NetworkTestFunction & NetworkTestFunctionWithCapacity) => void) {
	describe(title, () => {
		its(createNetworkTestFunction(false));
	});

	describe(`${title} (with validation)`, () => {
		its(createNetworkTestFunction(true));
	});
}

function describeNetworkNoValidation(
	title: string,
	its: (itFunc: NetworkTestFunction & NetworkTestFunctionWithCapacity) => void
) {
	describe(title, () => {
		its(createNetworkTestFunction(false));
	});
}
